package sort.test3_30;

public class MergeSort {

    public  int[]  mergeSort(int[] nums){
        if (nums.length==0){
            return null;
        }
        int[] temp=new int[nums.length];
        sort(nums,0, nums.length-1,temp);
        return  nums;
    }

    public  void sort(int[] nums,int lo,int hi,int[] temp){
        if (lo>=hi){
            return;
        }
        int mid=(lo+hi)/2;
        sort(nums,lo,mid,temp);
        sort(nums,mid+1,hi,temp);
        merge(nums,lo,mid,hi,temp);
    }

    public  void  merge(int[] nums,int lo,int mid,int hi,int[] temp){
        int i=0;
        int j=lo;
        int k=mid+1;
        while (j<=mid&&k<=hi){
            if (nums[j]<nums[k]){
                temp[i++]=nums[j++];
            }else{
                temp[i++]=nums[k++];
            }
        }

        while (j<=mid){
            temp[i++]=nums[j++];
        }
        while (k<=hi){
            temp[i++]=nums[k++];
        }
        for (int l = 0; l < i; l++) {
           nums[lo+l]=temp[l];
        }




    }

    public static void main(String[] args) {
      MergeSort mergeSort = new MergeSort();
        int[] a={4,2,1,3,8,6};
        int[] ints = mergeSort.mergeSort(a);
        for (int b: ints
        ) {
            System.out.println(b);

        }
    }




}
